// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-05 14:25
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.GraphyTrain.UFS;

import java.util.HashSet;

public class FindCircleNum {
    /**
     * 寻找省份数量 -> 寻找图中连通图的数量
     * 1 使用图的遍历方法直接计算
     * 2 使用并查集
     */
    int[] find;

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        // 并查集帮派查询路径
        find = new int[n];
        // 初始化并查集
        for (int i = 0; i < n; i++) {
            // 初始并查集的时候每一个元素的帮主都是它自己
            find[i] = i;
        }
        // 遍历无向图中的路径->进行合并帮派
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < isConnected[i].length; j++) {
                if (isConnected[i][j] == 1) {
                    // 当前节点存在路径，进行合并帮派
                    union(i, j);
                }
            }
        }
        HashSet<Integer> numSet = new HashSet<>();
        for (int i = 0; i < n; i++) {
            numSet.add(Find(i));
        }
        return numSet.size();
    }

    /**
     * 合并两个帮派
     *
     * @param x
     * @param y
     */
    private void union(int x, int y) {
        int xx = Find(x);
        int yy = Find(y);
        find[yy] = xx;
    }

    /**
     * 查找当前值得帮主
     */
    private int Find(int i) {
        if (find[i] != i) {
            return Find(find[i]);
        }
        return i;
    }
}
